// https://leetcode.cn/problems/satisfiability-of-equality-equations/

// 题干：给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，
//      并采用两种不同的形式之一："a==b" 或 "a!=b"。
//      在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
//      只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

// 示例：输入：["a==b","b!=a"]
//      输出：false

// 碎语：同样是并查集的应用

#include <bits/stdc++.h>
using namespace std;

class UnionFindSet
{
public:
    // 初始时，将数组中元素全部设置为-1
    UnionFindSet(size_t n)
            :_ufs(n, -1)
    {}

    // 给一个元素的编号，找到该元素所在集合的名称
    void Union(int x1, int x2)
    {
        int root1 = FindRoot(x1);
        int root2 = FindRoot(x2);

        // 如果本身就在一个集合，那么无需合并
        if (root1 == root2) return ;

        // 如果有需求下标小的作根，则交换一下root
//        if (root1 > root2) swap(root1, root2);

        // 如果不在同一个集合，则默认认为把x2代表集合合并到x1上，即x1作根，x2作子
        _ufs[root1] += _ufs[root2];

        // 将x2代表集合的名称改为x1
        _ufs[root2] = root1;
    }

    // 给一个元素的编号，找到该元素所在集合的名称
    int FindRoot(int x)
    {
        int parent = x;
        while (_ufs[parent] >= 0){
            parent = _ufs[parent];
        }

        return parent;
    }

    // 判断是不是在同一个集合
    bool isInset(int x1, int x2)
    {
        return FindRoot(x1) == FindRoot(x2);
    }

    // 计算一下有几个集合（树）
    size_t SetSize()
    {
        size_t size = 0;
        for (size_t i = 0 ; i < _ufs.size() ; i++){
            if (_ufs[i] < 0) size++;
        }

        return size;
    }
private:
    vector<int> _ufs; // 假设给的就是下标
};

class Solution
{
public:
    bool equationsPossible(vector<string>& equations)
    {
        UnionFindSet ufs(26);

        for (const auto& str : equations){
            if (str[1] == '='){
                ufs.Union(str[0] - 'a', str[3] - 'a');
            }
        }

        for (const auto& str : equations){
            if (str[1] == '!'){
                int root1 = ufs.FindRoot(str[0] - 'a');
                int root2 = ufs.FindRoot(str[3] - 'a');

                if (root1 == root2) return false;
            }
        }

        return true;
    }
};

int main()
{
    Solution sol;
    vector<string> equations = {"b==a","a==b"};

    cout << sol.equationsPossible(equations) << endl;

    return 0;
}

